% This is a sample LaTeX input file.  (Version of 9 April 1986) 
% 
% A '%' character causes TeX to ignore all remaining text on the line, 
% and is used for comments like this one.

\documentclass{article}    % Specifies the document style.
\usepackage[pdftex]{graphicx}
\usepackage{cancel}
\usepackage{setspace} % Import setspace package
\usepackage{url}
\usepackage[space]{grffile}
\usepackage{xskak}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{tikz}
\usepackage[bottom]{footmisc}
\bibliographystyle{ieeetran}
\usepackage[normalem]{ulem}
\usepackage{algorithmic}
\usepackage[nothing]{algorithm}
\usepackage[strict]{changepage}
\usepackage{soul}

\linespread{1.6} %Set the iine spacing
								% The preamble begins here.
\usepackage[retainorgcmds]{IEEEtrantools}
                   
\begin{document}           % End of preamble and beginning of text.
%\begin{titlepage}
%
%\title{Thesis proposal} % Declares the document's title. 
%\author{Andreas Bok Andersen \url{aboa@itu.dk}}    % Declares the author's name. 
%% Deleting this command produces today's date.
%
%\maketitle                 % Produces the title
%
%
%\end{center}
%\end{titlepage}

\begin{titlepage}

\begin{center}

%\vspace*{1cm}
\Large
\textsc{Master Thesis Proposal}\\

%\LARGE
\normalsize
\vspace{1cm}
Andreas Bok Andersen \url{aboa@itu.dk}\\
Student id: $3699764586$\\

\vspace{5cm}


\textsc{Supervisors:\\
Rasmus Pagh, IT University of Copenhagen \\
Lars Juhl Jensen, Center for Protein Research}\\
\vfill

\textsc{IT University of Copenhagen\\
Software Development and Technology}

\end{center}

\end{titlepage}

\section{Introduction}
Clustering is central in bioinformatics for finding eg. functional modules and protein families. However the data analysis is confronted with the problem of an exponential growth of data\cite{Levitt2007}.\\
Many different clustering algorithms exists, hierarchical, kkn, ao. I intend to focus on a specific clustering algorithm, using Hidden Markov Models (Markov Clustering, MCL), cf. section~\ref{sec:mcl} which has been used extensively in bioinformatics, cf. section~\ref{sec:relevance_mcl_bioinf}.\\

The central point of the thesis will be to investigate possible optimizations of the MCL algorithm.\\

Optimization with respect to time, I/O bound and space are to be considered, cf. section~\ref{sec:comp_aspects_mcl}.\\
A resulting implementation is to be tested on a parallel distributed system, cf. section~\ref{sec:experimental_part}.\\
Furthermore the implementation should be benchmarked against existing implementations of MCL\cite{Srihari2010}\cite{Kim2011}.\\
Finally the biological validity of the implementation should be tested, cf. section~\ref{sec:benchmarking}.\\\\

If the optimizations prove succesfull it could result in an improved data analysis tool for researchers in bioinformatics. \\
Results showing no improvement would verify the viability of the existing implementations. 
\pagebreak

\section{Markov Clustering (MCL) - A brief overview}\footnote{\url{http://jclust.embl.de/algorithms.html}}
\label{sec:mcl}
The MCL algorithm is a fast and scalable unsupervised clustering algorithm based on simulation of stochastic flow in graphs. The process deterministically computes the probabilities of random walks through a graph, and uses two operators transforming one set of probabilities into another. It does so by using the language of stochastic matrices (also called Markov matrices) which capture the mathematical concept of random walks on a graph. 

The basic idea underlying the MCL algorithm is that dense regions in sparse graphs correspond with regions in which the number of k-length paths is relatively large, for small k in N, which corresponds to multiplying probabilities in the matrix appropriately. Random walks of length k have higher probability (product) for paths with beginning and ending in the same dense region than for other paths.

The algorithm starts by creating a Markov matrix from the graph, where first, in the adjacency matrix, diagonal elements are added to include self-loops for all nodes, i.e., probabilities that the random walker stays at a particular node. After this initialisation, the algorithm works by alternating two operations, expansion and inflation, iteratively recomputing the set of transition probabilities. The expansion step corresponds to matrix multiplication (on stochastic matrices), the inflation step corresponds with a parametrized inflation operator $Gamma_r$, which acts column-wise on (column) stochastic matrices (here, we use row-wise operation, which is analogous).
 
The inflation operator transforms a stochastic matrix into another one by raising each element to a positive power p and re-normalising columns to keep the matrix stochastic. The effect is that larger probabilities in each column are emphasized and smaller ones deemphasized. On the other side, the matrix multiplication in the expansion step creates new non-zero elements, i.e., edges. The algorithm converges very fast, and the result is an idempotent Markov matrix, $M = M * M$, which represents a hard clustering of the graph into components.

A column stochastic matrix is a non-negative matrix with the property that each of its columns sums to 1. Given such a matrix $M$ and a real number $r > 1$, the column stochastic matrix resulting from inflating each of the
 columns of $M$ with power coefficient $r$ is written $\Gamma_{r}(M)$, and $\Gamma_{r}$ is called the inflation operator with power coefficient $r$. Write $\sum\limits_{r,j} M$ for the summation of all the entries in column 
$j$ of $M$ raised to the power $r$ (sum after taking powers). Then $\Gamma_{r}(M)$ is defined in an entrywise manner by setting 

$\Gamma_r(M_{ij}) =  M_{ij}^{r}  / \sum\limits_{r,j} M$
 
Expansion and inflation have two opposing effects: While expansion flattens the stochastic distributions in the columns and thus causes paths of a random walker to become more evenly spread, inflation contracts them to favoured paths.\footnote{The mathematical basis of the MCL algorithm is the subject of Stijn van Dongen's thesis Graph Clustering by Flow Simulation \url{ http://micans.org/mcl/index.html?sec_thesisetc}}

\begin{figure}
	\centering
		\includegraphics[width=1.00\textwidth]{C:/Users/Andreas/Documents/ITU/Thesis/flowchart_tribe-mcl.jpg}
		\caption{Flowchart of the MCL algorithm}
	\label{fig:flowchart_tribe-mcl}
\end{figure}

\begin{algorithm}
\caption{MCL Clustering Algorithm}
\label{MCLAlgorithm}
\begin{algorithmic}
   \STATE G is a graph
   \STATE add loops to G                             
   \STATE set $\Gamma$ to some value \COMMENT{\textit{	affects granularity}}
   \STATE set $M_1 $to be the matrix of random walks on G

   \WHILE{change} 
      \STATE $M_2 \gets  M_1 * M_1$                        \COMMENT{\textit{	expansion}}
      \STATE $M_1 \gets  \Gamma(M_2)$                           \COMMENT{\textit{	inflation}}
      \STATE $change \gets  difference(M_1, M_2)$
	\ENDWHILE
   \STATE set CLUSTERING as the components of $M_1$    
\end{algorithmic}
\end{algorithm}

\subsection{Computational aspects and challenges of MCL}
\label{sec:comp_aspects_mcl}
The time-complexity is $O(Nk^2)$ where n is the number of the nodes, k is the average or maximum number of edges that nodes are allowed to have. 
The space complexity is of order $O(N^2)$. 
The bounds are feasible in practice for small input sizes. But clustering $protein-sequences$ which involve ie. larger subsets of the human genes (in total $20000-25000$) mapped by the Human Genome Project\footnote{\url{http://www.ornl.gov/sci/techresources/Human_Genome/home.shtml}} renders the computation intractable with regard to space complexity and I/O operations needed for the $matrix-matrix$ multiplication, as the adjacency cannot be fitted into RAM.
Presently the techniques to optimization of time, $space/memory$ load lies in the pruning of intermediary MCL iterations.\\

\subsection{Optimization of MCL}
\subsection{Space}
Several areas could be considered for optimization
\paragraph{Cache oblivious strategy}
\cite{Piyush2000}\cite{Arge2007}\cite{Vignesh2010}\cite{Kumar2003a}\cite{Demaine2002}\\
\cite{Frigo2006} $ O(n^3/\sqrt{Z} + (Pn)^\frac{1}{3}n^2) $

\paragraph{Existing MCL Optimizations}
	\begin{itemize}	
		\item resource allocation 
		\item compilation options
		\item preprocessing/pruning
		\begin{itemize}
			\item not all edges in the graph are fully informative $\Rightarrow$ reduce number of edges per node 
			\item not sufficient contrast in the edge weights $\Rightarrow$ transformation
			\item the graph is very densely connected and shifting edge weights is not applicable $\Rightarrow$ increase contrast
		\end{itemize}		
	\end{itemize}
\subsection{Time}
\begin{itemize}
	\item Parallelization / cluster computing 
	\begin{itemize}
		\item Agarwal et.al \cite{Agarwal1994} Overlapped communication / Blas level 3 , optimizing communication cost, hypercube
		\item Alonso et. al\cite{Alonso2010} Heterogenous computational clusters. HPS > HDS 
		\item Choi \cite{Choi1998}, Blas level 3, Pipeline communication, 
		\item Li \cite{Keqin1998} Pipeline communication, 
		
	\end{itemize}
 \cite{Bustamam2010}\cite{Dhillon1999}\cite{Yoo2010}\cite{Olman2009}\cite{Chen2010a}
		\item	Optimization of maxtrix-matrix multiplication \cite{Chen2010}\cite{Wang2010a}\cite{BuluCc2010}\cite{Beaumont2001}\cite{Alonso2010}\cite{Bustamam2010a}\cite{Pagh2011}\cite{BuluCc2010}
\end{itemize}
	
\subsubsection[short]{Optimization of matrix-matrix multiplication}
Articles related to matrix-matrix multiplication 
Approximation algorithms for matrix-matrix multiplication. A quality of clusters could be measured as clusters found across multiple runs of MCL.  
	
\subsection{MCL Benchmark results}
Brohée and Helden 2006\cite{Brohee2006a}

\begin{figure}[hbtp]
\includegraphics[width=\linewidth]{./images/Brohee - Helden - Table1}
\end{figure}

\begin{figure}[hbtp]
\includegraphics[width=\linewidth]{./images/Brohee - Helden Table3}
\end{figure}

\section{Experimental part}
\label{sec:experimental_part}
Implementation of MCL on a cluster at DTU using a framework for parallel computing eg. MapReduce, Hadoop, NexisLexis\newline
I have access to a cluster of 96 nodes each with 2 quad core intel i5 processors. Each node has 12gb of RAM.\newline




\paragraph{Blas Level 3}


\subsection{HPC and bioinformatics}
\label{sec:hpc_bioinformatics}
MapReduce and Hadoop are widely used in bioinformatics for large scale distributed data analysis\cite{Taylor2010}. 
Another interesting framework is the High-Performance Computing Cluster software developed by NexisLexis Risk Solutions\cite{NexisNexisRiskSolutions2012}\cite{Middleton2011a}\cite{LexisNexisRiskSolutions2011}\cite{NexisNexisRiskSolutions2012}. \cite{Yoo2010} reported a significant performance improvement over Hadoop and MapReduce. Only recently, end of 2011, has the software been released to the open source community. No projects to my knowledge have implemented MCL on this framework. 

\begin{figure}[hbtp]
\includegraphics[width=\linewidth]{./images/HPCC_Architecture}
\end{figure}

Find matrix multiplication benchmarks\\
HADOOP
\begin{itemize}
\item Avro: A data serialization system.
\item Cassandra: A scalable multi-master database with no single points of failure.
\item Chukwa: A data collection system for managing large distributed systems.
\item HBase: A scalable, distributed database that supports structured data storage for large tables.
\item Hive: A data warehouse infrastructure that provides data summarization and ad hoc querying.
\item Mahout: A Scalable machine learning and data mining library.
\item Pig: A high-level data-flow language and execution framework for parallel computation.
\item ZooKeeper: A high-performance coordination service for distributed applications.
\end{itemize}

NexisLexis

\subsection{Benchmarking}
\label{sec:benchmarking}
Test computational performance of an optimized MCL implementation
\begin{itemize}
	\item Benchmark against\cite{Yoo2010}\cite{Hartley2006}
	\item 1TB sort or other standard benchmark test
	\item Scalability: What scaling factor is achieved
\end{itemize}

Test biological validity by testing clusterings against existing annotations of eg. protein families.
Performance for randomized graphs.


Brohée and Helden \cite{Brohee2006a} GRID database: Network interactions of Saccharomycs cerevisiae (yeast). 
Mass-spectrometry data yields best accuracy.

\section{MCL used in bioinformatics}
\label{sec:relevance_mcl_bioinf}
The MCL clustering have been used in several areas of bioinformatics, cf. below, thus giving an opportunity for verifying the biological validity of my implementation.
\begin{itemize}
	\item Protein-Protein interaction\cite{Asur2007}\cite{Vlasblom2009}\cite{Brohee2006a}
	\item Analyzing associated networks finding functional modules\cite{King2004}
	\item Finding protein families (orthogonal proteins) by anaylzing sequence similarity from Blast output  (Interpro, SCOP) \cite{Enright2002a}\ \cite{Kawaji2004}\cite{Bapat2010}\cite{Tetko2005a}
	\item Document clustering of Pubmed\cite{Theodosiou2008}, 
\end{itemize}

\section{Project Plan}
Fig. \ref{fig:timeline} is a preliminary plan for the project. \\
I have done a backgound literature search and collected all references in Mendeley. \\
I intend to write the thesis in English. \\
Most likely I will write the thesis in Latex, as the theoretical parts of the thesis would require mathematical notations.\\
With regard to supervison it would be helpful to have prescheduled meetings or dates where I send drafts$/$results.\\
I will be writing the thesis at Center for Protein Research and will thus have daily contact with Lars Juhl Jensen. However the formal distribution of supervision hours is yet undecided. 
\begin{figure}
\begin{adjustwidth}{-2cm}{-2cm}
	\includegraphics{C:/Users/Andreas/Documents/ITU/Thesis/timeline.png}
	\caption{Timeline}
	\label{fig:timeline}
	\end{adjustwidth}
\end{figure}

\pagebreak
\section{Thesis outline}

\begin{itemize}
	\item Introduction: a summary of the problem I intend to solve and my approach.
	\item Problem Statement: detailed description of the problem I am trying to solve.
	\item Background Research: description of the field in general and how others have tried to solve this problem.
	\item Bioinformatics and problems related to clustering
	\item Approach: Description of the MCL Algorithm. Theoretical/practical considerations for optimization. Potential weaknesses of my approach
	\item The Implementation: Analyze possible optimizations and describe how these have been implemented.
	\item Experiments: Description of method, experimental results and evaluation.
	\item Conclusion: Summary of the thesis. What conclusions can be drawn. Future work in this area.
\end{itemize}

\bibliography{Thesis}
\end{document}
% End of document.